package leetCode.solution;

import com.alibaba.fastjson.JSON;

public class Solution31 {
	public static void main(String[] args) {
		new Solution31().nextPermutation(new int[] {3,2,1});
	}
	public void nextPermutation(int[] nums) {
		int i = nums.length-2,j=nums.length-1;
		while(i>=0) {
			if(nums[i]<nums[j]) 
				break;
			i--;j--;
		}
		if(i<0) {
			reverse(nums,0,nums.length-1);
			return;
		}
		
		for(int k=nums.length-1;k>=j;k--) {
			if(nums[k]>nums[i]) {
				swap(nums,i,k);
				
				reverse(nums,j,nums.length-1);
				break;
			}
		}
		System.out.println(JSON.toJSON(nums));
	}
	void swap(int[] nums, int l, int r) {
		int tmp = nums[l];
		nums[l]=nums[r];
		nums[r]=tmp;
	}
	void reverse(int[] nums, int l, int r) {
		while(l<r) {
			int tmp = nums[l];
			nums[l]=nums[r];
			nums[r]=tmp;
			l++;r--;
		}
	}
	
	
}